<?php
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class Solution {
    public function insertIntoBST(TreeNode $root, $val)
    {
        if ($root == null) {
            return new TreeNode($val);
        }
        if ($val < $root->val) {
            $root->left = $this->insertIntoBST($root->left, $val);
        }
        if ($val > $root->right) {
            $root->right = $this->insertIntoBST($root->right, $val);
        }
        // if (root.val == val)
        //     BST 中一般不会插入已存在元素
        return $root;
    }
}